/*
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
    性质1：堆中某个结点的值总是不大于或不小于其父结点的值；
    性质2：堆总是一棵完全二叉树。
对于完全二叉树，若从上至下、从左至右编号，以根节点为0开始，则编号为i的节点，其左孩子节点编号为2i+1，右孩子节点编号为2i+2，父亲节点为 (i-1) / 2。
一棵节点个数为N的完全二叉树，其高度为 h = log 2 (N+1)（2为底数）。
 */

class Heap {
    constructor(sortFn) {
        this.sortFn = sortFn
        this.heapQueue = []
    }
    push(item) {
        this.heapQueue.push(item)
        this.adjustUp()
    }
    // 删除堆顶元素
    pop() {
        // 堆顶元素
        const out = this.heapQueue[0];
        // 移除堆顶元素 填入最后一个元素
        this.heapQueue[0] = this.heapQueue.pop();
        // 开始向下调整最后一个元素
        this.adjustDown()
        return out
    }
    // 堆销毁
    destroy() {
        this.heapQueue = []
    }
    /*
    堆的向上调整算法
    向上调整算法是从节点 n 开始，调整 节点n 到根节点 之间的路径上的节点（任一节点到根节点之间的路径唯一）。
    其结果是，将这条路径上，最大或者最小的节点，放到根节点位置。这个算法的前提是：这条路径，除了节点n，其余节点要满足堆的特性，即有序。
     */
    // [27,15,19,18,28,34,65,49,25,37]
    adjustUp() {
        let index = this.size() - 1; // 记录推入元素下标
        let parent = Math.floor((index - 1) / 2); // 记录父节点下标
        while (parent >= 0 && this.compare(parent, index) > 0) { // 注意compare参数顺序
            [this.heapQueue[index], this.heapQueue[parent]] = [this.heapQueue[parent], this.heapQueue[index]];
            // 更新下标
            index = parent;
            parent = Math.floor((index - 1) / 2);
        }
    }
    /*
     堆的向下调整算法
     我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是同一种堆（此处假设为小堆），才能调整。
     每一次，根节点都和左右孩子节点中，较小的那个孩子交换
     在此过程中，我们要明确几个问题：
        1、如何找到孩子节点？
            leftChild = parent * 2 + 1 rightChild = parent * 2 + 2  任一节点i的parent = (i - 1) / 2
        2、如何判断该孩子节点是否存在？（比如值为 28 的节点，不存在右孩子）
            child下标小于数组.length
        3、边界条件？什么时候停止调整？
            1)首先，由于其子树是小堆，所以如果调整到某个节点，其父亲节点比孩子节点都小，就不需要调整了
            2)其次，就是调整到最后一步的情况，如下。每次调整，改变的都是代表父亲节点和孩子节点 下标的那几个变量。
            父亲节点的值和孩子节点的值交换之后，下一轮调整 父亲节点的下标就变成了上一轮孩子节点的下标，孩子节点的下标变成当前 父亲节点的孩子节点中 小的那个的下标。
            所以孩子节点 > n，那么就代表调整到了最下面一层，不需要再调整了。
     */
    adjustDown() {
        let index = 0
        let left = index * 2 + 1
        let right = left + 1
        // 如果要求小堆栈，则当l-r > 0时 取的r为小的那个  如果要求大堆栈，当r - l >0时，取的r为大的那个.undefined判断在函数中
        let switchChild = this.compare(left,right) > 0 ? right : left
        // 循环终止条件为该节点为叶子。// 小堆栈时：index - s >0说明index比s大，需要换  大堆栈时：s - index >0 说明index比s小 所以需要换
        while(switchChild !==undefined && this.compare(index,switchChild) > 0) {
            // 交换两个值
            [this.heapQueue[index],this.heapQueue[switchChild]] = [this.heapQueue[switchChild],this.heapQueue[index]]
            // 下标更改
            index = switchChild
            left = index * 2 + 1
            right = left + 1
            switchChild = this.compare(left,right) > 0 ? right : left
        }
    }
    compare(index1,index2) {
        if (this.heapQueue[index1] === undefined) {
            return 1
        }
        // 代表右子树没有
        if (this.heapQueue[index2] === undefined) {
            return -1
        }
        // 根据返回正数或负数判断
        return this.sortFn(this.heapQueue[index1],this.heapQueue[index2])
        // return this.sortFn(index1,index2)
    }
    /*
    建堆(通过向下调整建堆)
    从有孩子节点的 节点开始调整。使变为同种堆
    建堆(通过向上调整建堆)
    从根节点到最后一个节点依次调整，这样就可以保证，每一条路径，除了n节点之前的节点，都是有序的
     */
    create() {

    }
    /*
    堆排序
     */
    sort() {

    }
    // 取堆顶元素
    peek() {
        return this.heapQueue[0]
    }
    // 堆的大小
    size() {
        return this.heapQueue.length;
    }
    // 堆判空
    empty() {
        return this.heapQueue.length
    }
}
